/* mntree/klist.c 
 * 
 * This file is part of mntree. 
 * 
 * mntree is free software: you can redistribute it and/or modify 
 * it under the terms of the GNU General Public License as published by 
 * the Free Software Foundation, either version 3 of the License, or 
 * (at your option) any later version. 
 * 
 * mntree is distributed in the hope that it will be useful, 
 * but WITHOUT ANY WARRANTY; without even the implied warranty of 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 
 * GNU General Public License for more details. 
 * 
 * You should have received a copy of the GNU General Public License 
 * along with mntree. If not, see <https://www.gnu.org/licenses/>
 */ 





#include <mntree/mntree.h>
#include <mntree/sys.h>



/* node will never be a father :-) */

struct mntree_node *mntree_init_node(struct mntree_node *parent, 
		struct mntree_node *node) {
	node->nnodes = 0;
	node->middle = NULL;
	node->parent = parent;

	node->next_bro = NULL;
	node->prev_bro = NULL;

	node->nmid = 0;

	node->value = 0;
	node->payload = NULL;

	if (parent) 
		parent->nnodes++;

	return node;
}


/* this is only for initial a tree, that it has got children.
 * if you use this to initial a child, a lot of memory (3 * mntree_node) 
 * will be used
 *
 * parent: initiallized
 * node: uninitiallized
 * */

struct mntree_node *mntree_init(struct mntree_node *parent, 
		struct mntree_node *node) {
	struct mntree_node *r, *l, *m;

	r = mntree_malloc(sizeof(struct mntree_node));
	m = mntree_malloc(sizeof(struct mntree_node));
	l = mntree_malloc(sizeof(struct mntree_node));

	mntree_init_node(node, r);
	mntree_init_node(node, m);
	mntree_init_node(node, l);

	r->value = INT_MAX;
	r->prev_bro = m;

	m->value = 0;
	m->next_bro = r;
	m->prev_bro = l;

	l->value = INT_MIN;
	l->next_bro = m;

	mntree_init_node(parent, node);

	node->middle = m;
	node->leftmost = l;
	node->rightmost = r;
	node->nmid = 1;

	return node;
}


/* insert node into node, sorting:
 *
 * [ n 100	node 120 	t 140  ] */

#define ABS(n) 		((n) > 0 ? n : -(n))


struct mntree_node *mntree_link(struct mntree_node *parent, 
		struct mntree_node *node) {
	struct mntree_node *n = parent->middle, *t, *best = NULL;
	int dir;

	while (!(n->value <= node->value && n->next_bro->value >= node->value)) {
		if (n->value > node->value) 
			n = n->prev_bro;

		else 
			n = n->next_bro;
	}

	/* real insert */

	t = n->next_bro;
	n->next_bro = node;
	node->next_bro = t;

	node->prev_bro = n;
	t->prev_bro = node;

	/* update the middle */

	dir = (parent->nnodes >> 1) - parent->nmid;

	if (!dir) 
		goto nochanging;

	else if (dir > 0) {
		/* middle is on the right of parent->middle */
		best = parent->middle;

		while (dir--) {
			best = best->next_bro;

			if (!parent->middle) {
				best = best->prev_bro;

				break;
			}
		}
	}

	else {
		best = parent->middle;
		dir = -dir;

		while (dir--) {
			best = best->prev_bro;

			if (!parent->middle) {
				best = best->next_bro;

				break;
			}
		}
	}

nochanging:
	++parent->nnodes;

	return node;
}


struct mntree_node *mntree_find(struct mntree_node *parent, 
		int value) {
	struct mntree_node *n = parent->middle;

	if (n->value == INT_MAX || n->value == INT_MIN || !n->value) 
		return NULL;

	for (;;) {
		if (n->value > value) 
			n = n->prev_bro;

		else if (n->value < value) 
			n = n->next_bro;

		else 
			return n;
	}
	
	return NULL;
}


/* 
 * this was mntree_free(), but I relized that, some nodes can be allocated on stack: that 
 * means we can not free it directly. 
 *
 * So, I use a callback, and can be call safely. */


int mntree_each(struct mntree_node *node, int (* callback) (struct mntree_node *)) {
	struct mntree_node *n, *t;

	if (!node->nnodes) {
		callback(node);

		return 0;
	}

	for (n = node->leftmost->next_bro; n != node->rightmost; n = t) {
		t = n->next_bro;

		callback(n);
	}

	callback(node);

	return 0;
}



